package arr

/*
详细参考：https://zhuanlan.zhihu.com/p/93795692

树状数组：可以理解为是一种分层的结构，例如一个数组中一共有八个数（1～8，二进制表示如下）
001 010 011 100 101 110 111 1000

构造树状数组，则[001]是一个分组C1，[001,010]区间是C2分组（t.Arr[2]存储的就是C2分组内的数字和）, 011是C3分组，[001,100]是C4分组（存储1~4的和）
对于一个数001，他所在的分组从底层到高层分别是C1[001], C2[001,010], C4[001,100],C8[001, 1000]；
由于t.Arr[x]存储的是x对应分区内的数字和，在对001处的值进行Update操作时，001所在的所有分组内的数字和均需要更新，
即依次更新C1 C2 C3 C4...直到遍历完001所在的所有分组,而我们该如何确定一个数所在的所有分组？？？
即对一个数字x，假设lowbit(x)为该数字最右边一个1连带着这个1之后的所有0（例如1100, lowbit为100）,则每次对x加上lowbit(x)即得到上一层分区在t.Arr
中对应的索引值, x减去lowbit(x)即得到他的下一层分组在t.Arr中j的索引值

1.单点修改（修改树状数组中的一个值）：O(logN)
2.区间查询：O(logN),查询前n个数的和或查询区间[a,b]的数字和

*/

type TreeArr struct {
	Arr []int
}

// 获取二进制最低位的1
// 例如：101100，获取最右边的1即: 100
// 在计算机中数字以补码的形式存储，如果一个数最低位为1000, 那么-x的补码为1000取反再+1（0111+1 -> 1000）
func (t *TreeArr) LowBit(x int) int {
	return (x) & (-x)
}

// 初始化时，直接将数字通过Update存入即可
func (t *TreeArr) Init(nums []int) {
	for i := 1; i <= len(nums); i++ {
		t.Update(i, nums[i])
	}
}

// 对节点i增加x
// 树状数组是分层结构，一个节点i可能属于多个分组，例如(001属于C1[001], C2[001,010], C3[001, 100], C4[001, 1000]分组)
// 所以如果更新了节点i，则i所属的所有分组的数字和均需要更新(例如我对001的值增加x，则C1,C2,C3,C4分组内的数字和均需要增加x)，即依次更新
// t.Arr[001](C1分组内数字和) t.Arr[010](C2分组内数字和) t.Arr[100](C3分组内数字和) t.Arr[1000](C4分组内数字和)
// 时间复杂度:O(logN)
func (t *TreeArr) Update(i, x int) {
	for pos := i; pos < len(t.Arr); pos += t.LowBit(pos) {
		t.Arr[pos] += x
	}
}

// 查询前n个数字的和
// 以011为例，其前缀和为[001, 011]，由两部分构成，一个是[001, 010], 一个是[011]，这里有一个规律，一个数的二进制表示中有几个1，
// 就表示其前缀和由几个区间构成，例如011中有两个1，则是由两个区间构成的，且将该数字每次减去其lowbit恰好得到构成该数字前缀和的其中一个区间
// 所以计算出构成前n个数的前缀和的所有区间，然后累计即可得到前缀和
// 时间复杂度O(logN)
func (t *TreeArr) Query(n int) int {
	var ans int
	for pos := n; pos > 0; pos -= t.LowBit(pos) {
		ans += t.Arr[pos]
	}
	return ans
}

// 查询[a,b]区间的和
func (t *TreeArr) QueryRange(a, b int) int {
	return t.Query(b) - t.Query(a-1)
}